public class Test1 {
    //leetcode 879 盈利计划
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        //状态表示：这个题目有两个需要满足的条件，一个事人员限制，因格式人数限制，所以需要使用三维的dp表来表示
        //dp[i][j][k]表示从前i个工作中选择，使得工作所用的人数不超过j，产生的利润大于等于k
        //状态转移方程：第i个工作分为选和不选，当不选的时候，dp[i][j][k] = dp[i-1][j][k]
        //当第i个工作选的时候，dp[i][j][k] = dp[i-1][j - group[i]][k - profit[i]];
        //初始化，因为需要用到i-1和j-group[i]、k-profit[i]，后面两个条件可以在循环中控制防止越界
        //当i为0的时候，i-1就会越界，所以当i为0时需要做出初始化，第0行表示从前0个工作中选择人数不超过
        //1、2、3...，利润超过k的计划数，因为没有工作，所以利润为0，初始化为0
        int len = group.length;
        int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
        int MOD = (int)1e9 + 7;
        //当i和k都为0时，意思是从前0个工作中选择，使得人数不超过j，利润不超过0，也就是不选择，那么这就满足一种计划
        for(int j = 0; j <= n; j++) dp[0][j][0] = 1;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    //保证当前工作需要的人数是小于j人的，且当前工作的利润是大于k的
                    //这里当j<group[i-1]的时候是一定不满足的，并且还会越界，所以就直接不进去
                    //但是当k<profit[i-1]的时候是符合我们的情况的，所以需要进入这个选择，但是为了防止越界
                    //我们的k就取0和k-profit[i-1]的最大值

                    //k - p[i] < 0 ：此时说明p[i] 过⼤，也就是利润太⾼。但是利润⾼，不正是我
                    //们想要的嘛？所以这个状态「不能舍去」。但是问题来了，我们的 dp 表是没有负数的
                    //下标的，这就意味着这些状态我们⽆法表⽰。其实，根本不需要负的下标，我们根据实
                    //际情况来看，如果这个任务的利润已经能够达标了，我们仅需在之前的任务中，挑选出
                    //来的利润⾄少为 0 就可以了。因为实际情况不允许我们是负利润，那么负利润就等价
                    //于利润⾄少为 0 的情况。所以说这种情况就等价于 dp[i][j][0] ，我们可以对 k
                    //- p[i] 的结果与 0 取⼀个 max 。
                    if (j >= group[i-1]) {
                        dp[i][j][k] += dp[i-1][j - group[i-1]][Math.max(0,k-profit[i-1])];
                    }
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return dp[len][n][minProfit];
    }

    //优化
    public int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) {
        //状态表示：这个题目有两个需要满足的条件，一个事人员限制，因格式人数限制，所以需要使用三维的dp表来表示
        //dp[i][j][k]表示从前i个工作中选择，使得工作所用的人数不超过j，产生的利润大于等于k
        //状态转移方程：第i个工作分为选和不选，当不选的时候，dp[i][j][k] = dp[i-1][j][k]
        //当第i个工作选的时候，dp[i][j][k] = dp[i-1][j - group[i]][k - profit[i]];
        //初始化，因为需要用到i-1和j-group[i]、k-profit[i]，后面两个条件可以在循环中控制防止越界
        //当i为0的时候，i-1就会越界，所以当i为0时需要做出初始化，第0行表示从前0个工作中选择人数不超过
        //1、2、3...，利润超过k的计划数，因为没有工作，所以利润为0，初始化为0
        int len = group.length;
        int[][] dp = new int[n + 1][minProfit + 1];
        int MOD = (int)1e9 + 7;
        //当i和k都为0时，意思是从前0个工作中选择，使得人数不超过j，利润不超过0，也就是不选择，那么这就满足一种计划
        for(int j = 0; j <= n; j++) dp[j][0] = 1;
        for (int i = 1; i <= len; i++) {
            for (int j = n; j >= group[i-1]; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    //保证当前工作需要的人数是小于j人的，且当前工作的利润是大于k的
                    dp[j][k] += dp[j - group[i-1]][Math.max(0,k-profit[i-1])];
                    dp[j][k] %= MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
}
